"""
失败，过不了1000，消耗内存太大
"""


class Solution:
    def nthUglyNumber(self, n: int) -> int:
        start = 0
        count = 0

        mem = {1: True, 2: True, 3: True, 5: True}

        while count != n:
            start += 1
            tmp = start

            for v in [2, 3, 5]:
                if tmp % v == 0:
                    tmp = tmp / v
                    break

            if tmp in mem:
                if mem[tmp]:
                    mem[start] = True
                    count += 1
                else:
                    mem[start] = False
            else:
                mem[start] = False

        return start


if __name__ == "__main__":
    print(Solution().nthUglyNumber(1000))
